In multimedia applications, video data contain effective information and redundant data. Since the redundant data are useless and does not need to be transmitted and there are much redundant data in the video data, the amount of video data may be reduced greatly by compressing the redundant data in the video data, and thus it may be made very convenient to store and process the video data in real time.
In the video data, the amount of the redundant data, that is, the redundancy degree, are characterized by significant temporal correlation in structure. This is because signals of most regions of an image change very slowly in general, and especially, the background portion nearly keeps unchanged. Hence, video signals have considerable correlation between adjacent frames, that is, temporal correlation. Thus, the video data may be compressed greatly if the temporal correlation may be eliminated.
At preset, motion estimation methods are used for eliminating the temporal correlation in general, that is, for data of a current frame of an image, the previous frame is first searched for the region best matched with the data, and then a motion vector of the data of the current frame relative to the data of the previous frame is calculated and the calculated motion vector is encoded. As can be seen from the above, the key factor in the motion estimation methods is to determine a motion vector.
In practice, a block matching method is used for implementing the motion estimation methods in general. In the block matching method, each frame of image is divided into two-dimensional N N pixel sub-blocks, and in general, N is 16. On the assumption that all the pixels in a sub-block have made a same translation motion, the neighbourhood window of a sub-block in the previous frame corresponding to an N N pixel sub-block in the current frame is searched for the sub-block best matched with the N N pixel sub-block, the displacement in the two-dimensional plane between the current sub-block and the best matched sub-block in the previous frame is the motion vector obtained by means of the motion estimation.
In the block matching method, a full search method is used for searching for the best matched sub-block in general. The full search method includes: for each macro block of the current frame, calculating the block matching value at each point in a given range (the neighbourhood in general) of the previous frame, regarding a matched point corresponding to the minimum block matching value as the optimum matched point, and regarding the motion vector corresponding to the optimum matched point as the motion vector of the current macro block, wherein each point in the neighbourhood is the matched point. In general, the block matching value is the sum of the absolute values of differences between the gray values of one-to-one pixels of the macro block and the corresponding block at a matched point in the searching range, that is, the sum of the absolute differences (SAD), is used for the block matching value. The corresponding block at a matched point, that is the matched macro block, is the block the top left corner point of which is the matched point and the size of which is equal to that of the macro block. The block matching value, that is, the SAD value, is calculated by the following formula:
      SAD    ⁡          (              u        ,        v            )        =            ∑              i        =        1            M        ⁢                  ∑                  j          =          1                N            ⁢                                                          I              c                        ⁡                          (                              i                ,                j                            )                                -                                    I              r                        ⁡                          (                                                i                  +                  u                                ,                                  j                  +                  v                                            )                                                  
wherein Ic(i,j) denotes the gray value of a pixel in the current macro block, Ir(i+u, j+v) denotes the gray value of the corresponding pixel in the matched macro block in a reference frame, herein namely the previous, and (u,v) denotes the motion vector.
As can be seen from the above, in the prior art, the full search method is used to search for a best matched sub-block so as to eliminate the temporal correlation by using the block matching method of the motion estimation methods. That is, searching must be performed at each point in a given neighbourhood. Such a searching process in traversing manner results in a huge amount of calculation. For example, supposing that searching is performed in a range of 32 32 points, that is, 1024 points, of the previous frame, 1024 points are to be calculated for each macro block. Thus, the speed of video data compression is decreased greatly and cannot meet the demand of the video data in real time.